package main

import "sort"

func insert(intervals [][]int, newInterval []int) (ans [][]int) {
	intervals = append(intervals, newInterval)
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	var tmp []int
	left, right := intervals[0][0], intervals[0][1]
	for i := 0; i < len(intervals); i++ {
		if intervals[i][0] < right {
			right = max(intervals[i][1], right)
		} else {
			tmp = []int{left, right}
			ans = append(ans, tmp)
			left, right = intervals[i][0], intervals[i][1]
		}
	}
	ans = append(ans, tmp)
	return ans
}

func insert2(intervals [][]int, newInterval []int) [][]int {
	res := make([][]int, 0)
	l := len(intervals)
	i := 0
	for i < l && intervals[i][1] < newInterval[0] {
		res = append(res, intervals[i])
		i++
	}
	for i < l && intervals[i][0] <= newInterval[1] {
		newInterval[0] = min(newInterval[0], intervals[i][0])
		newInterval[1] = max(newInterval[1], intervals[i][1])
		i++
	}
	res = append(res, newInterval)
	for i < l {
		res = append(res, intervals[i])
		i++
	}
	return res
}
